// https://www.lintcode.com/problem/middle-of-linked-list/description?_from=cat

/**
 * Definition of singly-linked-list:
 * class ListNode {
 * public:
 *     int val;
 *     ListNode *next;
 *     ListNode(int val) {
 *        this->val = val;
 *        this->next = NULL;
 *     }
 * }
 */

class Solution {
public:
    /**
     * @param head: the given linked list
     * @return: the array that store the values in reverse order 
     */
    ListNode *middleNode(ListNode *head) {   
        ListNode * first = head;
        ListNode * second = head;
        if (!first)
        {
            return NULL;
        }
        while (first->next && first->next->next)
        {
            first = first->next->next;
            second = second->next;
        }
        return second;
    }
};